package algorithms.question.class04;

import common.util.MyUtil;

/**
 * 字符串交错组成
 * <p>
 * https://leetcode.com/problems/interleaving-string/
 *
 * @author guichang
 * @date 2021/7/31
 */

@SuppressWarnings("all")
public class Code7_字符串交错组成 {
    // dp定义[i][j] 取str1的前i个字符，str2的前j个字符能否交错出str3的i+j
    // 判断最后一个字符与哪个相等

    public static void main(String[] args) {
        String str1 = "gui";
        String str2 = "chang";
        String str3 = "gchaungi";
        MyUtil.print(isInterleave(str1, str2, str3));
    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        int N1 = s1.length();
        int N2 = s2.length();
        int N3 = s3.length();

        if (N1 + N2 != N3) {
            return false;
        }
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        boolean[][] dp = new boolean[N1 + 1][N2 + 1];
        dp[0][0] = true;
        for (int i = 1; i <= N1; i++) {
            dp[i][0] = dp[i - 1][0] ? c1[i - 1] == c3[i - 1] : false;
        }
        for (int j = 1; j <= N2; j++) {
            dp[0][j] = dp[0][j - 1] ? c2[j - 1] == c3[j - 1] : false;
        }
        for (int i = 1; i <= N1; i++) {
            for (int j = 1; j <= N2; j++) {
                // i的最后一个和c3的相等
                boolean p1 = (c1[i - 1] == c3[i + j - 1]) && (dp[i][j] = dp[i - 1][j]);
                // j的最后一个和c3相等
                boolean p2 = (c2[j - 1] == c3[i + j - 1]) && (dp[i][j] = dp[i][j - 1]);
                // 两者求或
                dp[i][j] = p1 || p2;
            }
        }
        return dp[N1][N2];
    }

}